# import heapq
# import random
# li = list(range(100))
# random.shuffle(li)
# print(li)
#
# heapq.heapify(li) # 建小根堆
# n = len(li)
# for  i in range(n):
#     print(heapq.heappop(li),end=',')

import random
# 时间复杂度 log(N)
def sift(li, low, high):
    """
    li:列表
    low：堆的根节点位置
    high：堆的最后一个元素的位置
    """
    i = low  # 把根节点拿出来
    j = 2 * i + 1  # 左孩子
    tmp = li[low]  # 把根节点的数据存起来
    while j <= high:  # 只要j没有越界就一直循环
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子比较大
            j = j + 1  # J指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j  # 向下调整
            j = 2 * i + 1
        else:  # tmp更大，把tmp放在更大的地方
            li[i] = tmp  # 把tmp放在某一领导级的位置上
            break
    else:
        li[i] = tmp  # 把tmp放在叶子节点
# 时间复杂度 nlog(n)
def heap_sort(li):
    """
    使用sift函数来写堆排序
    农村包围城市
    遍历所有的非叶子节点
    """
    n = len(li)
    for i in range((n-2)//2, -1, -1):
        # i表示建堆的时候
        sift(li, i, n-1)
    # 建堆完成
    for i in range(n-1, -1, -1):
        li[0],li[i] = li[i],li[0]
        sift(li,0,i-1)
    return li
li = list(range(100))
random.shuffle(li)
print(li)
li = heap_sort(li)
print(li)
